package com.nine.algorithm.recursion.pascaltriangle;

/**
 * @author nine
 * @version 1.0
 * @description 杨辉三角-优化性能问题【使用二维数组记忆法】
 * @date 24/5/3 11:26
 */
public class PascalTriangle2 {


	/**
	 * @param triangle 二维数组存放值
	 * @param i        行
	 * @param j        列
	 * @return 元素的值
	 */
	private static int element(int[][] triangle, int i, int j) {
		// 优化返回，没优化之前是 O(2^n)，优化之后O(n^2)
		if (triangle[i][j] > 0) {
			return triangle[i][j];
		}

		// 第一列、行和列相同时，返回1
		if (j == 0 || i == j) {
			triangle[i][j] = 1;
			return 1;
		}
		triangle[i][j] = element(triangle, i - 1, j - 1) + element(triangle, i - 1, j);
		return triangle[i][j];
	}

	public static void print(int n) {
		// 定义二维数组，存放对于杨辉三角的元素值
		int[][] triangle = new int[n][];
		for (int i = 0; i < n; i++) {
			triangle[i] = new int[i + 1];
			printSpace(n, i);
			for (int j = 0; j <= i; j++) {
				System.out.printf("%-4d", element(triangle, i, j));
			}
			System.out.println();
		}
	}

	/**
	 * 打印空格
	 *
	 * @param n 行数
	 * @param i 第几行
	 */
	public static void printSpace(int n, int i) {
		int num = (n - 1 - i) * 2;
		for (int j = 0; j < num; j++) {
			System.out.print(" ");
		}
	}


	public static void main(String[] args) {
		// 计算某一行某一列的元素值
		// System.out.println(element(4, 2));
		print(10);
	}


}
